#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL<<60);

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    // 示例：全源最短路径（有向图）
    int n=4;
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
    for(int i=0;i<n;i++) dist[i][i]=0;
    auto add=[&](int u,int v,long long w){ dist[u][v]=min(dist[u][v], w); };
    add(0,1,5); add(0,3,10);
    add(1,2,3);
    add(2,3,1);
    // 运行 Floyd-Warshall
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dist[i][k]<INF/2 && dist[k][j]<INF/2)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    // 输出
    cout << "Floyd-Warshall 全源最短距离矩阵:" << '\n';
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(dist[i][j]>=INF/2) cout << "INF";
            else cout << dist[i][j];
            if(j+1<n) cout << '\t';
        }
        cout << '\n';
    }
    return 0;
}

